/**
 * 剑指Offer 面试题25
 * 二叉树中和为某一值的路径 
 * 时间限制：1秒  空间限制：32768K
 * 
 * 题目描述：
 * 输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
 * 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
 */

package com.cyy.test_t_2_;


import com.cyy.test.util.TreeNode;

import java.util.ArrayList;
import java.util.Stack;

public class t_25 {

	public static void main(String[] args) {
		TreeNode p1 = new TreeNode(10);
		TreeNode p2 = new TreeNode(5);
		TreeNode p3 = new TreeNode(12);
		TreeNode p4 = new TreeNode(4);
		TreeNode p5 = new TreeNode(7);
		p1.left = p2;
		p1.right = p3;
		p2.left = p4;
		p2.right = p5;
		
		FindPath(p1,22);
	}
	
	public static ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target){
		ArrayList<ArrayList<Integer>> pathList = new ArrayList<ArrayList<Integer>>();
		if(root == null)
			return pathList;
		Stack<Integer> stack = new Stack<Integer>();
		FindPath(root,target,stack,pathList);
		return pathList;
	}
	
	private static void FindPath(TreeNode root,int target,
			Stack<Integer> path,
			ArrayList<ArrayList<Integer>> pathList){
		if(root == null)	return;
		if(root.left == null && root.right == null){
			if(root.val == target){
				 System.out.println("路径开始");
				ArrayList<Integer> list = new ArrayList<Integer>();
				for(int i : path){
					list.add(new Integer(i));
					 System.out.print(i+",");  
				}
				System.out.print(root.val);  
				System.out.println("");
				list.add(new Integer(root.val));
				pathList.add(list);
			}
		}
		else {
			path.push(new Integer(root.val));
			FindPath(root.left,target - root.val,path,pathList);
			FindPath(root.right,target - root.val,path,pathList);
			path.pop();
		}
	}

}
